package com.yiguang.algorithm.dp;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

import com.alibaba.fastjson.JSON;

/*
 * 二维平面dp
 * 329. 矩阵中的最长递增路径
 * 该题对变量及其变化理解更加深刻
 */
public class TwoDIncrementalPath {

	public List<Integer> longPath(int[][] grid) {
		List<Integer> result = new ArrayList();
		int maxLong = 0;
		int rowLength = grid.length;
		int colLength = grid[0].length;
		for(int i=0; i<rowLength; i++) {
			for(int j=0; j<colLength; j++) {
				System.out.println(i+","+j);
				List<Integer> currentList = new ArrayList();
				currentList.add(grid[i][j]);
				List<Integer> currentArr = dfs(grid, i, j, rowLength, colLength, currentList);
				if(currentArr.size()>result.size()) {
					result=currentArr;
				}
			}
		}
		return result;
	}
	
	public List<Integer> dfs(int[][] grid, int row, int column, int rowLength, int colLength, List<Integer> currentList) {
		
		List<Integer> topList = new ArrayList();
		List<Integer> rightList = new ArrayList();
		List<Integer> bottomList = new ArrayList();
		List<Integer> leftList = new ArrayList();
		// top
		if(row-1>=0 && grid[row][column]<grid[row-1][column]) {
			List<Integer> maxList = new ArrayList(currentList);
			maxList.add(grid[row-1][column]);
			topList = dfs(grid, row-1, column, rowLength, colLength, maxList);
		}
		// right
		if(column+1<colLength && grid[row][column]<grid[row][column+1]) {
			List<Integer> maxList = new ArrayList(currentList);
			maxList.add(grid[row][column+1]);
			rightList = dfs(grid, row, column+1, rowLength, colLength, maxList);
		}
		// bottom
		if(row+1<rowLength && grid[row][column]<grid[row+1][column]) {
			List<Integer> maxList = new ArrayList(currentList);
			maxList.add(grid[row+1][column]);
			bottomList = dfs(grid, row+1, column, rowLength, colLength, maxList);
		}
		// left
		if(column-1>=0 && grid[row][column]<grid[row][column-1]) {
			List<Integer> maxList = new ArrayList(currentList);
			maxList.add(grid[row][column-1]);
			leftList = dfs(grid, row, column-1, rowLength, colLength, maxList);
		}
		if(topList.size()>currentList.size()) {
			currentList = topList;
		}
		if(rightList.size()>currentList.size()) {
			currentList = rightList;
		}
		if(bottomList.size()>currentList.size()) {
			currentList = bottomList;
		}
		if(leftList.size()>currentList.size()) {
			currentList = leftList;
		}
		System.out.println(JSON.toJSONString(currentList));
		return currentList;
	}

	public static void main(String[] args) {
		/*
		 * 994
		 * 668
		 * 211
		 */
		int[][] matrix = {{3,4,5},{3,2,6},{2,2,1}};
		TwoDIncrementalPath twoDIncrementalPath = new TwoDIncrementalPath();
		List<Integer> result = twoDIncrementalPath.longPath(matrix);
		System.out.println(JSON.toJSONString(result));
	}

}
